The output devices of personal computers often include bitmap graphics devices. A bitmap graphics device typically includes a graphics adapter, which has a display memory, and a display screen. The bitmap graphics device inputs a bitmap to be displayed and then displays that bitmap on the display screen. A bitmap is a matrix of bits that defines an image that is to be displayed in a rectangular area on a display screen. Each bit in a bitmap corresponds to one picture element (pixel) on the display screen. To display computer output data, a bitmap graphics device reads the bitmap stored in the display memory and renders the corresponding image on the display screen. If a bit in the display memory is 1, then the bitmap graphics device turns on the corresponding pixel on the display screen. If a bit in the display memory is 0, then the bitmap graphics device turns off the corresponding pixel on the display screen. By changing the contents of the display memory, for instance, by loading a new bitmap, a computer program can effect a change on the display screen.
A computer program typically generates a bitmap in program memory, and then copies the bitmap to the display memory. Copying from program memory to display memory can be relatively time-consuming because bitmaps are often quite large and can contain one million or more bits. To improve performance and facilitate computer programming, typical graphically-oriented operating systems provide routines that are optimized to copy bitmaps from program memory to display memory. These routines are known as bit block-transfer (bitBLT) routines. In general, these bitBLT routines can read as input a source bitmap and a destination bitmap, which is typically in display memory. These bitBLT routines copy the source bitmap to the destination bitmap in an efficient manner.
BitBLT routines are optimized to copy a computer word of data at a time, rather than just a single bit at a time. A computer word is a number of bits that the computer operates on as a unit. Computer words typically comprise 8, 16, or 32 bits.
FIGS. 1A and 1B are diagrams of a display memory showing the results of various bitBLT operations. FIG. 1A shows the display memory before executing the bitBLT routine, and FIG. 1B shows the display memory after executing the bitBLT routine. FIGS. 1C and 1D are diagrams of the display screen corresponding to FIGS. 1A and 1B, respectively.
FIG. 2 is a diagram showing sample source bitmaps of an image of an arrow. The outlined arrow bitmap 201 is a matrix of bits that is 32 bits high by 32 bits wide. To display the outlined arrow bitmap 201 on the display screen at location 111, a program, when calling a bitBLT routine, would specify that the outlined arrow bitmap 201 is the source bitmap and specify that the display memory bitmap 101 is the destination bitmap corresponding to location 111 on the display screen. The bitBLT routine then copies the outlined arrow bitmap 201 to the display memory bitmap 101. When the outlined arrow bitmap 201 is copied to the display memory bitmap 101, the bits in the 32 by 32 bit matrix in the display memory bitmap 101 are overwritten by the outlined arrow bitmap 201 as shown by display memory bitmap 105. To display the solid arrow bitmap 202 on the display screen at location 112, a program would specify that the solid arrow bitmap 202 is the source bitmap and specify that the display memory bitmap 102 is the destination bitmap corresponding to location 112 on the display screen. The bitBLT routine then copies the solid arrow bitmap 202 to the display memory bitmap 102. The bits in the 32 by 32 bit matrix in the display memory bitmap 102 are overwritten by the solid arrow bitmap 202, as shown by display memory bitmap 106.
In certain situations, a program may want to display an arrow that is transparent. A transparent arrow is shown displayed at location 117 on the display screen. The transparent arrow is an arrow in which the underlying screen display is left intact except for the outline of the arrow. To provide this capability, typical bitBLT routines, in addition to copying bitmaps, permit Boolean logic operations to be performed on a bit-by-bit basis on the source and destination bitmaps. For example, to generate the transparent arrow as shown at location 117, the program specifies the outlined arrow bitmap 201 as the source bitmap, the display memory bitmap 103 as the destination bitmap, and the AND operation when invoking the bitBLT routine. The bitBLT routine retrieves each bit from the outlined arrow bitmap 201 and the corresponding bit from the display memory bitmap 103, performs the AND operation on the bits, and stores the result in the display memory bitmap 103, resulting in the display memory bitmap 107.
Although the bitBLT routines that perform copying and Boolean operations on source and destination bitmaps provide considerable flexibility, there are certain computer graphics operations that require invoking these bitBLT routines more than once. For example, if a program were to output an arrow as shown at location 118, the program would first invoke the bitBLT routine specifying the solid arrow bitmap 202 as the source bitmap, the display memory bitmap 104 as the destination bitmap, and the AND operation. The program would then invoke the bitBLT routine specifying the arrow bitmap 203 as the source bitmap, the display memory bitmap 104 as the destination bitmap, and the exclusive-OR operation. The invoking of the bitBLT routine twice results in each bit in the destination bitmap 108 being read from and written to twice. When a destination bitmap is large, the reading and writing of each bit twice can result in unacceptable performance.
Because copying large bitmaps can be expensive, typical bitBLT routines have been generalized to allow two source bitmaps to be designated, along with a destination bitmap and a Boolean operation. For example, to generate the arrow at location 118, the invoking program would designate solid arrow bitmap 202 as the first source bitmap (S.sub.1), arrow bitmap 203 as the second source bitmap (S.sub.2), and display memory bitmap 104 as the destination bitmap (D), along with Boolean operations that specify S.sub.1 is to be logically ANDed with D, and that the result is to be logically exclusive-ORed with S.sub.2. In standard Boolean algebra notation, that function would be specified as: EQU (S.sub.1 & D).sym.S.sub.2
where & represents the Boolean AND operator and where .sym. represents the Boolean exclusive-OR operator.
Although it is possible to develop bitBLT routines that provide Boolean operations on an arbitrary number of source bitmaps, in practice, bitBLT routines typically support only two source bitmaps. When two source bitmaps are designated, the three bitmaps S.sub.1, S.sub.2, and D can be combined using Boolean operators in 256 unique ways. Each way of combining the three bitmaps is referred to as a logical operation or a raster operation.
TABLE I ______________________________________ S.sub.1 1 1 1 1 0 0 0 0 S.sub.2 1 1 0 0 1 1 0 0 Boolean D 1 0 1 0 1 0 1 0 Function ______________________________________ Result: 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 (S.sub.2 .vertline.D)' 0 0 1 1 0 0 1 1 S.sub.2 ' 0 1 0 0 0 1 0 0 S.sub.2 & D' 0 1 0 1 0 1 0 1 D' 0 1 0 1 1 0 1 0 S.sub.1 .sym. D 0 1 1 0 0 1 1 0 S.sub.2 .sym. D 0 1 1 0 1 1 0 0 (S.sub.2 & D) .sym. S.sub.1 1 0 0 0 1 0 0 0 S.sub.2 & D 1 0 1 1 1 0 1 1 S.sub.1 '.vertline.D 1 1 0 0 0 0 0 0 S.sub.2 & S.sub.1 1 1 0 0 1 1 0 0 S.sub.2 1 1 1 0 1 1 1 0 S.sub.2 .vertline.D 1 1 1 1 0 0 0 0 S.sub.1 1 1 1 1 1 0 1 1 S.sub.2 '.vertline.S.sub.1 .vertline.D 1 1 1 1 1 1 1 1 1 ______________________________________
Table I shows a subset of the 256 logical operations which designate how the S.sub.1, S.sub.2, and D bitmaps can be combined. The column entitled "Boolean Function" shows the Boolean function, comprised of bitmaps and Boolean operators, which generates the corresponding result.
TABLE II ______________________________________ S.sub.1 S.sub.2 D S.sub.1 & D (S.sub.1 & D) .sym. S.sub.2 ______________________________________ 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 1 0 0 0 0 1 0 1 1 1 1 1 0 0 1 1 1 1 1 0 ______________________________________
For example, to generate display memory bitmap 108, the program specifies the bit string "01101100" (hexadecimal 6C.sub.H) as the logical operation to be performed. The logical operation 6C.sub.H specifies the result for each of the eight possible combination of values for S.sub.1, S.sub.2, and D. Table II shows the values of the input bitmaps and the intermediate and final results achieved by the Boolean function corresponding to logical operation 6C.sub.H.
TABLE III ______________________________________ for h = 0, Height for w = 0, Width D[h,w] = (S.sub.1 [h,w] & D[h,w]) .sym. S.sub.2 [h,w] endfor endfor ______________________________________
Table III illustrates pseudocode for the bitBLT routine that implements the logical operation 6C.sub.H. The variable Height represents the number of rows in each bitmap and the variable Width represents the number of columns of bits in each bitmap divided by the word width. In this example, the width of each bitmap is assumed to be an integral number of computer words.
TABLE IV ______________________________________ MOV h, height outerloop: MOV w, width innerloop: MOV di, S.sub.1 [h,w] common MOV si, S.sub.2 [h,w] MOV dx, D[h,w] logical MOV ax, di operation- -- AND ax, dx specific XOR ax, si MOV D[h,w], ax DEC w JNZ innerloop common DEC h JNZ outerloop ______________________________________
Table IV shows Intel 80386 assembly language pseudocode that implements the logical operation 6C.sub.H. Typical prior art bitBLT routines may have a separate section of code to implement each of the 256 logical operations. However, some bitBLT routine implementations recognize that a portion of the code is common to all logical operations and a portion of the code is logical operation-specific. As shown in Table IV, the three middle statements are the logical operation-specific code for the logical operation 6C.sub.H. In this code, these three statements load the ax register with S.sub.1 bitmap, logically AND the D bitmap into the ax register, and then logically exclusive-OR the S.sub.2 bitmap with the ax register. The five statements preceding and the five statements following the logical operation-specific code control the looping through the bitmaps and are common to all logical operations.
To improve performance, prior art bitBLT routines store the logical operation-specific code for each of the 256 logical operations in a table and store just one copy of the common code. When the bitBLT routine is called with a logical operation designation, such as 6C.sub.H, the bitBLT routine generates the code to implement the logical operation by retrieving the appropriate logical operation-specific code from the table and combining the retrieved code with the common code. The bitBLT routine then executes the generated code to perform the logical operation. The process of generating the code to execute is referred to as bitBLT compiling.
These prior art bitBLT routines generate efficient code at execution time. However, these routines require the storage of 256 logical operation-specific code segments. In addition, it can take considerable programming effort to develop and test these 256 code segments.